package interview.firstmissingpositive;

public class FirstMissingPositive {
	public int firstMissingPositive(int[] num) {
		for(int i = 0; i < num.length; i++) {
			while(num[i] != i + 1) {
				if(num[i] <= 0 || num[i] > num.length || num[i] == num[num[i] - 1])
					break;
				int tmp = num[i];
				num[i] = num[tmp - 1];
				num[tmp - 1] = tmp;
			}
		}
		
		for(int i = 0; i < num.length; i++) {
			if(num[i] != i + 1)
				return i + 1;
		}
		
		return num.length + 1;
	}
}
